#include <iostream>
#include "BinaryTree.h"
using namespace std;

int main()
{
    cout << "----------Test01: BST----------" << endl ;

    BinarySearchTree<int> bst;
    int NUMS_BST = 38;
    const int GAP_BST = 11;
    int i_bst;

    cout << "Checking... (Success when outputting only a column of numbers from smallest to largest.)" << endl;

    for( i_bst = GAP_BST; i_bst != 0; i_bst = ( i_bst + GAP_BST ) % NUMS_BST )
        bst.insert( i_bst );

    for( i_bst = 1; i_bst < NUMS_BST; i_bst += 2 )
        bst.remove( i_bst );

    if( NUMS_BST < 40 )
        bst.printTree( );
    if( bst.findMin( ) != 2 || bst.findMax( ) != NUMS_BST - 2 )
        cout << "FindMin or FindMax error!" << endl;

    for( i_bst = 2; i_bst < NUMS_BST; i_bst += 2 )
        if( !bst.contains( i_bst ) )
            cout << "Find error1!" << endl;

    for( i_bst = 1; i_bst < NUMS_BST; i_bst += 2 ) {
        if( bst.contains( i_bst ) )
            cout << "Find error2!" << endl;
    }

    BinarySearchTree<int> bst2;
    bst2 = bst;

    for( i_bst = 2; i_bst < NUMS_BST; i_bst += 2 )
        if( !bst2.contains( i_bst ) )
            cout << "Find error1!" << endl;

    for( i_bst = 1; i_bst < NUMS_BST; i_bst += 2 ) {
        if( bst2.contains( i_bst ) )
            cout << "Find error2!" << endl;
    }

    cout << "----------Test02: AVL----------" << endl ;

    AvlTree<int> avl;
    int NUMS_AVL = 38;
    const int GAP_AVL = 22;
    int i_avl;

    cout << "Checking... (Success when outputting only a column of numbers from smallest to largest.)" << endl;

    for( i_avl = GAP_AVL; i_avl != 0; i_avl = ( i_avl + GAP_AVL ) % NUMS_AVL )
        avl.insert( i_avl );
    avl.remove( 0 );
    for( i_avl = 1; i_avl < NUMS_AVL; i_avl += 2 )
        avl.remove( i_avl );

    if( NUMS_AVL < 40 )
        avl.printTree( );
    if( avl.findMin( ) != 2 || avl.findMax( ) != NUMS_AVL - 2 )
        cout << "FindMin or FindMax error!" << endl;

    for( i_avl = 2; i_avl < NUMS_AVL; i_avl += 2 )
        if( !avl.contains( i_avl ) )
            cout << "Find error1!" << endl;

    for( i_avl = 1; i_avl < NUMS_AVL; i_avl += 2 ) {
        if( avl.contains( i_avl )  )
            cout << "Find error2!" << endl;
    }

    AvlTree<int> avl2;
    avl2 = avl;

    for( i_avl = 2; i_avl < NUMS_AVL; i_avl += 2 )
        if( !avl2.contains( i_avl ) )
            cout << "Find error1!" << endl;

    for( i_avl = 1; i_avl < NUMS_AVL; i_avl += 2 ) {
        if( avl2.contains( i_avl ) )
            cout << "Find error2!" << endl;
    }

    cout << "----------Test03: RBT----------" << endl ;

    const int NEG_INF = -9999;
    RedBlackTree<int> t{ NEG_INF };
    int NUMS = 400000;
    const int GAP  =   37;
    int i;

    cout << "Checking... (no more output means success)" << endl;

    for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
        t.insert( i );

    if( NUMS < 40 )
        t.printTree( );
    if( t.findMin( ) != 1 || t.findMax( ) != NUMS - 1 )
        cout << "FindMin or FindMax error!" << endl;

    for( i = 1; i < NUMS; ++i )
        if( !t.contains( i ) )
            cout << "Find error1!" << endl;
    if( t.contains( 0 ) )
        cout << "Oops!" << endl;

    
    RedBlackTree<int> t2{ NEG_INF };
    t2 = t;

    for( i = 1; i < NUMS; ++i )
        if( !t2.contains( i ) )
            cout << "Find error1!" << endl;
    if( t2.contains( 0 ) )
        cout << "Oops!" << endl;

    cout << "----------Test04: SPLAY----------" << endl ;
    SplayTree<int> splay;
    int NUMS_SPLAY = 38;
    const int GAP_SPLAY = 22;
    int i_splay;

    cout << "Checking... (Success when outputting only a column of numbers from smallest to largest.)" << endl;

    for( i_splay = GAP_SPLAY; i_splay != 0; i_splay = ( i_splay + GAP_SPLAY ) % NUMS_SPLAY )
        splay.insert( i_splay );

    for( i_splay = 1; i_splay < NUMS_SPLAY; i_splay += 2 )
        splay.remove( i_splay );

    if( NUMS_SPLAY < 40 )
        splay.printTree( );
    if( splay.findMin( ) != 2 || splay.findMax( ) != NUMS_SPLAY - 2 )
        cout << "FindMin or FindMax error!" << endl;

    for( i_splay = 2; i_splay < NUMS_SPLAY; i_splay += 2 )
        if( !splay.contains( i_splay ) )
            cout << "Find error1!" << endl;

    for( i_splay = 1; i_splay < NUMS_SPLAY; i_splay += 2 ) {
        if( splay.contains( i_splay ) )
            cout << "Find error2!" << endl;
    }

    SplayTree<int> splay2;
    splay2 = splay;

    for( i_splay = 2; i_splay < NUMS_SPLAY; i_splay += 2 )
        if( !splay2.contains( i_splay ) )
            cout << "Find error1!" << endl;

    for( i_splay = 1; i_splay < NUMS_SPLAY; i_splay += 2 ) {
        if( splay2.contains( i_splay ) )
            cout << "Find error2!" << endl;
    }

    cout << "Test completed." << endl;
    return 0;
}